'''
Created on 04/12/2012

@author: GabrielBacelar
'''
visited = {
0: ((5, 5), 'LStart', 0, 0, 0), 
1: ((5, 4), 'South', 1, 1, 1, 0),
2: ((4, 5), 'West', 1, 1, 2, 0), 
3: ((5, 5), 'East', 1, 2, 3, 2),
4: ((3, 5), 'West', 1, 2, 4, 2), 
5: ((4, 5), 'East', 1, 3, 5, 4),
6: ((2, 5), 'West', 1, 3, 6, 4), 
7: ((3, 5), 'East', 1, 4, 7, 6),
8: ((1, 5), 'West', 1, 4, 8, 6), 
9: ((1, 4), 'South', 1, 5, 9, 8),
10: ((2, 5), 'East', 1, 5, 10, 8), 
11: ((1, 5), 'North', 1, 6, 11, 9),
12: ((1, 3), 'South', 1, 6, 12, 9), 
13: ((1, 4), 'North', 1, 7, 13, 12),
14: ((2, 3), 'East', 1, 7, 14, 12), 
15: ((2, 2), 'South', 1, 8, 15, 14),
16: ((1, 3), 'West', 1, 8, 16, 14), 
17: ((2, 3), 'North', 1, 9, 17, 15),
18: ((2, 1), 'South', 1, 9, 18, 15), 
19: ((3, 2), 'East', 1, 9, 19, 15),
20: ((4, 2), 'East', 1, 10, 20, 19), 
21: ((2, 2), 'West', 1, 10, 21, 19),
22: ((4, 3), 'North', 1, 11, 22, 20), 
23: ((3, 2), 'West', 1, 11, 23, 20),
24: ((4, 2), 'South', 1, 12, 24, 22), 
25: ((5, 3), 'East', 1, 12, 25, 22),
26: ((5, 4), 'North', 1, 13, 26, 25), 
27: ((4, 3), 'West', 1, 13, 27, 25),
28: ((5, 5), 'North', 1, 14, 28, 26), 
29: ((5, 3), 'South', 1, 14, 29, 26),
30: ((2, 2), 'North', 1, 10, 30, 18), 
31: ((1, 1), 'West', 1, 10, 31, 18)
}
 
#state = 31: ((1, 1), 'West', 1, 10, 31, 18)
state = ((1, 1), 'West', 1, 10, 31, 18)
#State[-1] is parent node key, state[-2] is current node key. [-3] is cumulative cost and [-4] is stepcost, I just include them always because its a generic function and I need those for others.
 
def makeList(visited,state,ExplList=[],ExplList2=[]):
    if not visited[state[-1]] in ExplList:
        ExplList.append(visited[state[-1]])
        ExplList2.append(state[1])
        return makeList(visited,visited[state[-1]],ExplList,ExplList2)
    else:
        ExplList2.reverse()
        return ExplList2

print makeList(visited, state)


#['West', 'West', 'West', 'West', 'South', 'South', 'East', 'South', 'South', 'West']